package lcr;

import java.util.*;

public class Test0151 {
}

class Solution0151_1 {
    public List<List<Integer>> decorateRecord(TreeNode root) {
        ArrayList<List<Integer>> ans = new ArrayList<>();
        if (root == null) return ans;
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(root);

        bfs(deque, ans);

        return ans;
    }

    public void bfs(Deque<TreeNode> deque, ArrayList<List<Integer>> ans){
        int size = deque.size();
        ArrayList<Integer> list = new ArrayList<>();

        for (int i = 0; i < size; i++){
            TreeNode node = deque.poll();
            list.add(node.val);

            if (node.left != null) deque.offer(node.left);
            if (node.right != null) deque.offer(node.right);
        }

        ans.add(list);
        if (!deque.isEmpty())rBfs(deque, ans);
    }

    public void rBfs(Deque<TreeNode> deque, ArrayList<List<Integer>> ans){
        int size = deque.size();
        ArrayList<Integer> list = new ArrayList<>();

        for (int i = 0; i < size; i++){
            TreeNode node = deque.pollLast();
            list.add(node.val);

            if (node.right != null) deque.push(node.right);
            if (node.left != null) deque.push(node.left);
        }

        ans.add(list);
        if (!deque.isEmpty())bfs(deque, ans);
    }
}
